public class MyLinkedList {
     static class ListNode{
          public int val;
          public ListNode next;
          public ListNode prev;

          public ListNode(int val){
               this.val = val;
          }
     }
     public ListNode head;
     public ListNode last;//尾指针
     //头插法
     public void addFirst(int data){
          ListNode node = new ListNode(data);
          if(head == null){
               head = node;
               last = node;
          }else{
               node.next = head;
               head.prev = node;
               head = node;
          }
     }
     //尾插法
     public void addLast(int data){
          ListNode node = new ListNode(data);
          if(head == null){
               head = node;
               last = node;
          }else{
               last.next = node;
               node.prev = last;
               last = node;
          }
     }
     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index,int data) throws IndexIllegality{
          //检查index是否合法
          if(index < 0 || index > size()){
              //抛异常
               throw new IndexIllegality("index位置不合法"+index);
          }
          if(index == 0){
               //头插法
               addFirst(data);
               return;
          }
          if(index == size()){
               //尾插法
               addLast(data);
               return;
          }

          ListNode node = new ListNode(data);
          ListNode cur = findIndex(index);
          node.next = cur;
          cur.prev.next = node;
          node.prev = cur.prev;
          cur.prev = node;


     }
     //找到index位置
     private ListNode findIndex(int index){
          ListNode cur = head;
          while (index != 0){
               cur = cur.next;
               index--;
          }
          return cur;
     }
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
          ListNode cur = this.head;
          while(cur != null){
               if(cur.val == key) {
                    return true;
               }
               cur = cur.next;
          }
          return false;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key){
          ListNode cur = this.head;
          while(cur != null){
               if (cur.val == key){
                    if(cur == head){
                         head = head.next;//head == null
                         if(head == null){
                              last = null;
                         }else{
                              head.prev = null;
                         }

                    }else{
                         cur.prev.next = cur.next;
                         if(cur.next == null){
                              last = last.prev;
                         }else{
                              cur.next.prev = cur.prev;
                         }
                    }
                    return;
               }else{
                    cur = cur.next;
               }
          }
     }
     //删除所有值为key的节点
     public void removeAllKey(int key){
          ListNode cur = this.head;
          while(cur != null){
               if (cur.val == key){
                    if(cur == head){
                         head = head.next;//head == null
                         if(head == null){
                              last = null;
                         }else{
                              head.prev = null;
                         }

                    }else{
                         cur.prev.next = cur.next;
                         if(cur.next == null){
                              last = last.prev;
                         }else{
                              cur.next.prev = cur.prev;
                         }
                    }
               }
               cur = cur.next;
          }
     }
     //得到单链表的长度
     public int size(){
          ListNode cur = this.head;
          int count = 0;
          while(cur != null){
               count++;
               cur = cur.next;
          }
          return count;
     }

     public void display(){
          ListNode cur = this.head;
          while(cur != null){
               System.out.print(cur.val + " ");
               cur = cur.next;
          }
          System.out.println();
     }

     public void clear(){
          //暴力置空
//          head = null;
//          last = null;

          //每个节点都置空
          ListNode cur = head;
          while (cur != null){
               ListNode curNext = cur.next;
               cur.prev = null;
               cur.next = null;
               cur = curNext;
          }
          head = null;
          last = null;
     }
 }